{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Insertion Steps to Make a String Palindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minInsertions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #让字符串成为回文串的最少插入次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，每一次操作你都可以在字符串的任意位置插入任意字符。</p>\n",
    "\n",
    "<p>请你返回让&nbsp;<code>s</code>&nbsp;成为回文串的&nbsp;<strong>最少操作次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>「回文串」是正读和反读都相同的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"zzazz\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串 \"zzazz\" 已经是回文串了，所以不需要做任何插入操作。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"mbadm\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>字符串可变为 \"mbdadbm\" 或者 \"mdbabdm\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leetcode\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>插入 5 个字符后字符串变为 \"leetcodocteel\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 500</code></li>\n",
    "\t<li><code>s</code>&nbsp;中所有字符都是小写字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-insertion-steps-to-make-a-string-palindrome](https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-insertion-steps-to-make-a-string-palindrome](https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"zzazz\"', '\"mbadm\"', '\"leetcode\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        arr1 = [0] * n\n",
    "        i = n - 1\n",
    "        while i >= 0:\n",
    "            arr2 = [0] * n\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    arr2[j] = arr1[j - 1]\n",
    "                    continue\n",
    "                arr2[j] = min(arr1[j], arr2[j - 1]) + 1\n",
    "            arr1 = arr2\n",
    "            i -= 1\n",
    "        return arr1[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minInsertions(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         t = s[::-1]\n",
    "#         寻找最长公共子序列，也是为了寻找序列的最长回文子序列，之后对于不在回文子序列中的字符，依据在回文中心的左右两侧，在对侧填补相同字符\n",
    "#         dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "#         for i in range(1,n+1):\n",
    "#             for j in range(1,n+1):\n",
    "#                 dp[i][j] = max(dp[i-1][j],dp[i][j-1])\n",
    "#                 if s[i-1] == t[j-1]:\n",
    "#                     dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)\n",
    "#         return n - dp[n][n]\n",
    "\n",
    "# 动态区间规划\n",
    "# dp[i][j] 表示对于字符串 s 的子串 s[i:j] 最少添加的字符数量使满足要求\n",
    "class Solution:\n",
    "    def minInsertions(self,s:str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for span in range(2,n + 1):\n",
    "            for i in range(n- span + 1):\n",
    "                j = i + span -1\n",
    "                dp[i][j] = min(dp[i+1][j],dp[i][j-1]) + 1\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(dp[i][j],dp[i+1][j-1])\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = int(1e9)\n",
    "\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]\n",
    "        for sep in range(len(s)+1):\n",
    "            lf = s[:sep]\n",
    "            rt = s[sep:]\n",
    "            rt = rt[::-1]\n",
    "            m, n = len(lf), len(rt)\n",
    "            dif = abs(m - n)\n",
    "            min_len = min(m, n)\n",
    "            \n",
    "\n",
    "            def val(x, y):\n",
    "                return 0 if x<0 or y<0 else dp[x][y]\n",
    "            \n",
    "            for j in range(len(rt)):\n",
    "                if lf != '' and rt != '':\n",
    "                    if lf[sep-1] == rt[j]:\n",
    "                        dp[sep][j] = val(sep-1,j-1)+1\n",
    "                    else:\n",
    "                        dp[sep][j] = max(val(sep-1, j), val(sep, j-1))\n",
    "            ans = min(ans, dif + (min_len-dp[sep][len(rt)-1])*2) \n",
    "\n",
    "        dp = [[0]*(len(s)+1) for _ in range(len(s)+1)]\n",
    "        for sep in range(len(s)):\n",
    "            lf = s[:sep]\n",
    "            rt = s[sep+1:]\n",
    "            rt = rt[::-1]\n",
    "            m, n = len(lf), len(rt)\n",
    "            dif = abs(m - n)\n",
    "            min_len = min(m, n)\n",
    "            \n",
    "\n",
    "            def val(x, y):\n",
    "                return 0 if x<0 or y<0 else dp[x][y]\n",
    "            \n",
    "            for j in range(len(rt)):\n",
    "                if lf != '' and rt != '':\n",
    "                    if lf[sep-1] == rt[j]:\n",
    "                        dp[sep][j] = val(sep-1,j-1)+1\n",
    "                    else:\n",
    "                        dp[sep][j] = max(val(sep-1, j), val(sep, j-1))\n",
    "            ans = min(ans, dif + (min_len-dp[sep][len(rt)-1])*2)  \n",
    "    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        s1 = s[::-1]\n",
    "        length = len(s)\n",
    "        dp = [[0] * (length+1) for _ in range(length+1)]\n",
    "        for k in range(length+1):\n",
    "            dp[k][0] = k\n",
    "            dp[0][k] = k\n",
    "        for i in range(1, length+1):\n",
    "            for j in range(1, length+1):\n",
    "                if s[i-1] != s1[j-1]:\n",
    "                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1\n",
    "                else:\n",
    "                    dp[i][j] = dp[i-1][j-1] \n",
    "        return dp[-1][-1] // 2\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        dp = [[float('inf') for _ in range(len(s))] for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 0\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == j + 1:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i - 1][j + 1]\n",
    "                else:\n",
    "                    if i == j + 1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i][j + 1], dp[i - 1][j]) + 1\n",
    "        return dp[-1][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        memo = [[-1] * len(s) for _ in range(len(s))]\n",
    "        def dp(a, b):\n",
    "            if a >= b:\n",
    "                return 0\n",
    "            if memo[a][b] > -1:\n",
    "                return memo[a][b]\n",
    "            if s[a] == s[b]:\n",
    "                res = dp(a+1, b-1)\n",
    "            else:\n",
    "                res = min(dp(a, b-1), dp(a + 1, b)) + 1\n",
    "            memo[a][b] = res\n",
    "            return res\n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        def dp(i ,j):\n",
    "            if i >= j: return 0\n",
    "            if self.memo[i][j] != -1: return self.memo[i][j]\n",
    "            if s[i] == s[j]: self.memo[i][j] = dp(i+1, j-1)\n",
    "            else:\n",
    "                self.memo[i][j] = min(dp(i+1, j), dp(i, j-1))+1\n",
    "            return self.memo[i][j]\n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp_table = [[-1]*n for _ in range(n)]\n",
    "\n",
    "        def dp(s, l, r):\n",
    "            if dp_table[l][r] != -1:\n",
    "                return dp_table[l][r]\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            if s[l] == s[r]:\n",
    "                res = dp(s, l+1, r-1)\n",
    "            else:\n",
    "                res = 1+min(\n",
    "                    dp(s, l+1, r),\n",
    "                    dp(s, l, r-1),\n",
    "                )\n",
    "            dp_table[l][r] = res\n",
    "            return res\n",
    "        return dp(s, 0, len(s)-1)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        def dp(i, j, s):\r\n",
    "            if i > j:\r\n",
    "                return 0\r\n",
    "            \r\n",
    "            if memo[i][j] != -1:\r\n",
    "                return memo[i][j]\r\n",
    "            \r\n",
    "            if s[i] == s[j]:\r\n",
    "                memo[i][j] = dp(i + 1, j - 1, s)\r\n",
    "            else:\r\n",
    "                memo[i][j] = min(dp(i + 1, j, s) + 1, dp(i, j - 1, s) + 1)\r\n",
    "            \r\n",
    "            return memo[i][j]\r\n",
    "                \r\n",
    "\r\n",
    "        \r\n",
    "        memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]\r\n",
    "\r\n",
    "        return dp(0, len(s) - 1, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.s = s\n",
    "        self.rec = {}\n",
    "        x = self.dfs(0, len(s) - 1)\n",
    "        return x\n",
    "\n",
    "\n",
    "    def dfs(self, i, j):\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        if (i, j) in self.rec:\n",
    "            return self.rec[(i, j)]\n",
    "        if self.s[i] == self.s[j]:\n",
    "            self.rec[(i, j)] = self.dfs(i + 1, j - 1)\n",
    "        else:\n",
    "            self.rec[(i, j)] = min(self.dfs(i + 1, j) + 1, self.dfs(i, j -1) + 1)\n",
    "        return self.rec[(i, j)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        self.memo = {}\n",
    "        for i in range(len(s)):\n",
    "            ans = max(self.dp(s, i, i), ans)\n",
    "\n",
    "        return len(s) - ans\n",
    "\n",
    "    def dp(self, s, i, j):\n",
    "        if i < 0 or j >= len(s):\n",
    "            return 0\n",
    "\n",
    "        if (i, j) in self.memo:\n",
    "            return self.memo[(i, j)]\n",
    "\n",
    "        if i == j:\n",
    "            self.memo[(i, j)] = max(1 + self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j))\n",
    "        elif s[i] == s[j]:\n",
    "            self.memo[(i, j)] = max(2 + self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j)) \n",
    "        else:\n",
    "            self.memo[(i, j)] = max(self.dp(s, i - 1, j + 1), self.dp(s, i, j + 1), self.dp(s, i - 1, j))\n",
    "\n",
    "        return self.memo[(i, j)] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ok(self,s,t):\n",
    "        n = len(s)\n",
    "        m = len(t)\n",
    "        dp=[[[0,0,0,0] for j in range(m+1)]for i in range(n+1)]\n",
    "        ma = 0\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,m+1):\n",
    "                dp[i][j][0]=max(dp[i][j-1][2],dp[i-1][j][1],dp[i-1][j-1][3],dp[i][j-1][0],dp[i-1][j][0])\n",
    "                if(s[i-1]==t[j-1]):\n",
    "                    dp[i][j][3]=max(dp[i-1][j][1]+1,dp[i][j-1][2]+1,dp[i-1][j][0]+1,dp[i][j-1][0]+1)\n",
    "                    try:\n",
    "                        dp[i][j+1][1]=dp[i][j][3]\n",
    "                    except:pass\n",
    "                    try:\n",
    "                        dp[i+1][j][2]=dp[i][j][3]\n",
    "                    except:pass\n",
    "                else:\n",
    "                    dp[i][j][1] = max(dp[i][j-1][1],dp[i][j][1])\n",
    "                    dp[i][j][2] = max(dp[i-1][j][2],dp[i][j][2])\n",
    "        ma=max(dp[n][m])\n",
    "        #for i in dp:print(i)\n",
    "        return ma\n",
    "        kk=0\n",
    "        j=0\n",
    "        for i in range(len(t)):\n",
    "            if(s[j]==t[i]):\n",
    "                kk+=1\n",
    "        return kk\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        kk=0;nooo=0\n",
    "        nn=self.ok(s,s[-1::-1])\n",
    "        return n-nn\n",
    "        for i in range(n-1):\n",
    "            s1=s[i::-1];s2=s[i+2:]\n",
    "            s3=s[i+1:]\n",
    "            kk3=self.ok(s1,s3)\n",
    "            kk1=self.ok(s1,s2)\n",
    "            #print(kk1,kk3,s1,s2,s3)\n",
    "            if(kk3>kk and kk3>kk1):\n",
    "                #print(kk3)\n",
    "                nooo=1\n",
    "            if(kk1>=kk and kk1>=kk3):\n",
    "                #print(kk1,\"?\")\n",
    "                nooo=0\n",
    "            kk=max(kk1,kk,kk3)\n",
    "        if(nooo==1):n+=1\n",
    "        return n-kk*2-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        q = deque()\n",
    "        q.append([0, s])\n",
    "        runed = set()\n",
    "        while q:\n",
    "            step, tmps = q.popleft()\n",
    "            if len(tmps) <= 1:\n",
    "                return step\n",
    "            if tmps[0] == tmps[-1]:\n",
    "                c = tmps[1:-1]\n",
    "                if c in runed:\n",
    "                    continue\n",
    "                runed.add(c)\n",
    "                q.appendleft([step, c])\n",
    "            else:\n",
    "                c = tmps[1:]\n",
    "                if c not in runed:\n",
    "                    runed.add(c)\n",
    "                    q.append([step + 1, c])\n",
    "                c = tmps[:-1]\n",
    "                if c not in runed:\n",
    "                    runed.add(c)\n",
    "                    q.append([step + 1, c])\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        self.memo = {}\n",
    "        return self.min_insert(s)\n",
    "\n",
    "    def min_insert(self, s):\n",
    "        if s in self.memo:\n",
    "            return self.memo[s]\n",
    "\n",
    "        length = len(s)\n",
    "        half = int(length / 2)\n",
    "        addtion = 1 if length % 2 == 1 else 0\n",
    "\n",
    "        if length <= 1 or s[:half] == s[half + addtion:]:\n",
    "            self.memo[s] = 0\n",
    "            return 0\n",
    "        elif length == 2:\n",
    "            self.memo[s] = 1\n",
    "            return 1\n",
    "\n",
    "        last = length - 1\n",
    "        first = 0\n",
    "        while first < last and s[first] == s[last]:\n",
    "            first += 1\n",
    "            last -= 1\n",
    "\n",
    "        if first >= last:\n",
    "            return 0\n",
    "\n",
    "        self.memo[s] = min(self.min_insert(s[first + 1:last + 1]), self.min_insert(s[first:last])) + 1\n",
    "        return self.memo[s]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "class Solution:\n",
    "    def __init__(self) -> None:\n",
    "        self.dict = {}\n",
    "    @functools.lru_cache\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 0 if s[0] == s[-1] else 1\n",
    "        if s in self.dict:\n",
    "            return self.dict[s]\n",
    "        if s[0] == s[-1]:\n",
    "            res = self.minInsertions(s[1:n-1])\n",
    "        else:\n",
    "            l = self.minInsertions(s[:n-1])\n",
    "            r = self.minInsertions(s[1:])\n",
    "            res = min(l,r)+1\n",
    "        self.dict[s] = res\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.dp = {}\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        res = s[::-1]\n",
    "        return len(s) - len(self.longestCommonSubsequence(s, res))\n",
    "\n",
    "    def longestCommonSubsequence(self,text1: str, text2: str) -> int:\n",
    "        text1_idx, text2_idx = \\\n",
    "            len(text1) - 1, len(text2) - 1\n",
    "        key = '%s-%s' % (text1_idx, text2_idx)\n",
    "        if key in self.dp.keys():\n",
    "            return self.dp[key]\n",
    "        tmp_sub_seq = ''\n",
    "        while text1_idx >= 0 and text2_idx >= 0:\n",
    "            if text1[text1_idx] == text2[text2_idx]:\n",
    "                tmp_sub_seq = text1[text1_idx] + tmp_sub_seq\n",
    "                text1_idx, text2_idx = \\\n",
    "                    text1_idx - 1, text2_idx - 1\n",
    "            else:\n",
    "                tmp1 = self.longestCommonSubsequence(text1[:text1_idx],\n",
    "                                                text2[:text2_idx+1])\n",
    "                tmp2 = self.longestCommonSubsequence(text1[:text1_idx+1],\n",
    "                                                text2[:text2_idx])\n",
    "                tmp_sub_seq = (tmp1 if len(tmp1) > len(tmp2) else tmp2) + tmp_sub_seq\n",
    "                break\n",
    "        self.dp[key] = tmp_sub_seq\n",
    "        return tmp_sub_seq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minInsertions(self, s: str) -> int:\r\n",
    "        df = {(i,j):0 for i in range(len(s)) for j in range(len(s))}\r\n",
    "        for d in range(1,len(s)):\r\n",
    "            for i in range(len(s) - d):\r\n",
    "                j = i + d\r\n",
    "                if s[i] == s[j]:\r\n",
    "                    df[(i,j)] = df[(i+1,j-1)]\r\n",
    "                else:\r\n",
    "                    df[(i,j)] = min(df[(i+1,j)], df[(i,j-1)]) + 1\r\n",
    "        # print(df)\r\n",
    "        return df[(0,len(s)-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]\n",
    "\n",
    "        memo = {}\n",
    "\n",
    "        def helper(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return dp[i][j]\n",
    "            if i == j:\n",
    "                dp[i][j] = 0\n",
    "                memo[i, j] = True                \n",
    "            if i == j - 1:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = 0\n",
    "\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "                memo[i, j] = True\n",
    "            if i < j - 1:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = min(helper(i + 1, j - 1), helper(i, j - 1) + 1, helper(i + 1, j) + 1)\n",
    "                else:\n",
    "                    dp[i][j] = min(helper(i + 1, j - 1) + 2,\n",
    "                                   helper(i, j - 1) + 1, helper(i + 1, j) + 1)\n",
    "                memo[i,j] = True\n",
    "            return dp[i][j]\n",
    "        helper(0, len(s) - 1)\n",
    "        return dp[0][len(s) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        # 定义尝试模型\n",
    "        # 返回s[l:r+1]成为回文串的最少操作次数\n",
    "        dp = {}\n",
    "        def p(l, r):\n",
    "            # base case\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            # 记忆化搜索\n",
    "            name = '{},{}'.format(l, r)\n",
    "            if name in dp:\n",
    "                return dp[name]\n",
    "\n",
    "            # 状态转移\n",
    "            # 情况一，如果s[l] == s[r], 那么只需要把中间变成回文串就可以了\n",
    "            if s[l] == s[r]:\n",
    "                res = p(l+1, r-1)\n",
    "            # 情况二，如果s[l] != s[r], 那么就只需要交叉插入2个(bdc->bcdcb),\n",
    "            # 或者使用p将s[l+1:r]变成回文，然后加一个就可以(bcc->bccb)\n",
    "            else:\n",
    "                res = min(p(l+1, r-1) + 2, p(l+1, r) + 1, p(l, r-1) + 1)\n",
    "            dp[name] = res\n",
    "            return res\n",
    "        times = p(0, len(s) - 1)\n",
    "        return times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        # dp = [[0]*len(s) for _ in s]\n",
    "        # for i in range(len(s)):\n",
    "        #     dp[i][i] = 1\n",
    "        #     for j in range(i-1,-1,-1):\n",
    "        #         if s[i]==s[j]:\n",
    "        #             dp[i][j] = dp[i-1][j+1]+2\n",
    "        #         else:\n",
    "        #             dp[i][j]=max(dp[i][j+1],dp[i-1][j])\n",
    "        # return len(s) - dp[-1][0]\n",
    "        @lru_cache(30000)\n",
    "        def dp(i:int,j:int)->int:\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1,j-1)+2\n",
    "            return max(dp(i+1,j),dp(i,j-1))\n",
    "        return len(s)-dp(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        left, right = 0, len(s) - 1\n",
    "        cache = {}\n",
    "\n",
    "        def count_ops(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "\n",
    "            if (i, j) in cache:\n",
    "                return cache[(i, j)]\n",
    "\n",
    "            if s[i] == s[j]:\n",
    "                cache[(i, j)] = count_ops(i + 1, j - 1)\n",
    "                return cache[(i, j)]\n",
    "            \n",
    "            cache[(i, j)] = 1 + min(count_ops(i, j - 1), count_ops(i + 1, j))\n",
    "            return cache[(i, j)]\n",
    "        \n",
    "        return count_ops(left, right)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i + 1, j - 1)\n",
    "\n",
    "            return 1 + min(dfs(i, j - 1), dfs(i + 1, j))\n",
    "        return dfs(0, len(s) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dp(i, j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1, j-1)\n",
    "            return 1+min(dp(i, j-1), dp(i+1, j))\n",
    "        \n",
    "        return dp(0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "\n",
    "        mem = {}\n",
    "\n",
    "        def dfs(s, l, r):\n",
    "            if (l,r) in mem:\n",
    "                return mem[(l,r)]\n",
    "            rv = 0\n",
    "            if l >= r:\n",
    "                rv = 0\n",
    "            elif s[l] == s[r]:\n",
    "                rv = dfs(s, l+1, r-1)\n",
    "            else:\n",
    "                rv = min(dfs(s, l+1, r-1)+2, dfs(s, l+1, r)+1, dfs(s, l, r-1)+1)\n",
    "\n",
    "            mem[(l,r)] = rv\n",
    "            return rv\n",
    "\n",
    "        return dfs(s, 0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        idxes = collections.defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            idxes[ch].append(i)\n",
    "            \n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def helper(i, j):\n",
    "            if i >= j: return 0\n",
    "            I = idxes[s[i]]\n",
    "            res = helper(i + 1, j) + 1\n",
    "            ind1 = bisect.bisect_left(I, i)\n",
    "            ind2 = bisect.bisect_right(I, j)\n",
    "            # for idx in I:\n",
    "            #     if idx <= i:continue\n",
    "            #     if idx > j: break\n",
    "            #     res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            # return res\n",
    "            \n",
    "            # for k in range(ind1, ind2):\n",
    "            #     idx = I[k]\n",
    "            #     res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            \n",
    "            if ind2 > ind1:\n",
    "                idx = I[ind2 - 1]\n",
    "                res = min(res, helper(i + 1, idx - 1) + j - idx)\n",
    "            \n",
    "            return res\n",
    "            \n",
    "            \n",
    "            # res1 = helper(i + 1, j - 1) if s[i] == s[j] else j - i + 1\n",
    "            # return min(res1, 1 + helper(i + 1, j))\n",
    "        \n",
    "        \n",
    "        return helper(0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j:return 0\n",
    "            if s[i]==s[j]:return dfs(i+1,j-1)\n",
    "            return 1+min(dfs(i,j-1),dfs(i+1,j))\n",
    "        return dfs(0,len(s)-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            else:\n",
    "                return min(dfs(i,j-1),dfs(i+1,j)) + 1\n",
    "        return dfs(0,len(s)-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dp(i+1, j-1)\n",
    "            else:\n",
    "                return 1 + min(dp(i+1, j), dp(i, j-1))\n",
    "        \n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def getcount(left,right):\n",
    "            while left<=right and s[left]==s[right]:\n",
    "                left+=1\n",
    "                right-=1\n",
    "            if right<=left:\n",
    "                return 0\n",
    "            return 1+min(getcount(left+1,right),getcount(left,right-1))\n",
    "        return getcount(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        return self.dp(s,0,len(s)-1)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dp(self,s,i,j):\n",
    "        if i==j:\n",
    "            return 0\n",
    "        elif i+1==j:\n",
    "            return 0 if s[i]==s[j] else 1\n",
    "        else:\n",
    "            if s[i]==s[j]:\n",
    "                return self.dp(s,i+1,j-1)\n",
    "            else:\n",
    "                return min(self.dp(s,i+1,j),self.dp(s,i,j-1))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>=j: return int(i==j)\n",
    "            \n",
    "            if s[i]==s[j]:\n",
    "                return dfs(i+1,j-1)+2\n",
    "            else:\n",
    "                return min(dfs(i,j-1),dfs(i+1,j))+2\n",
    "        \n",
    "\n",
    "        def make_ans(i,j):\n",
    "            if i>j: return \"\"\n",
    "            if i==j: return s[i]\n",
    "            if s[i]==s[j]:\n",
    "                return s[i]+make_ans(i+1,j-1)+s[j]\n",
    "            if dfs(i,j-1)<=dfs(i+1,j):\n",
    "                return s[j]+make_ans(i,j-1)+s[j]\n",
    "            else:\n",
    "                return s[i]+make_ans(i+1,j)+s[i]\n",
    "        \n",
    "        n=len(s)\n",
    "        return dfs(0,n-1)-n\n",
    "        return len(make_ans(0,n-1))-n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minInsertions(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        #记忆化递归\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i:int ,j:int):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 0\n",
    "            if s[i]==s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j)+1,dfs(i,j-1)+1)\n",
    "        return dfs(0,n-1)\n",
    "        '''\n",
    "        #动态规划\n",
    "        # dp=[[0]*(n+1) for _ in range(n+1)]\n",
    "        # for i in range(n-1,-1,-1):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if s[i]==s[j]:\n",
    "        #             dp[i][j]=dp[i+1][j-1]\n",
    "        #         else:\n",
    "        #             dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1\n",
    "        # return dp[0][n-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return dfs(i+1,j-1)\n",
    "            return min(dfs(i+1,j)+1,dfs(i,j-1)+1)\n",
    "        return dfs(0,n-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
